/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-17
 * Time: 14:58
 */
public class Solution {
    //方法二动态规划
    public int begin;
    public int maxLen=1;
    public String longestPalindrome(String s) {
        int length=s.length();
        if(length<2){
            return s;
        }

        char[] src=s.toCharArray();
        boolean[][] arr=new boolean[length][length];
        //先把单独一个的设置为true
        for(int i=0;i<length;i++){
            arr[i][i]=true;
        }

        //注意因为判断[i][j]需要依赖[i+1][j-1],即需要依赖左下角的元素,所以按列从左往右判断
        for(int j=1;j<length;j++){
            for(int i=0;i<j;i++){
                //不相等一定不是回文子串
                if(src[i]!=src[j]){
                    arr[i][j]=false;
                }else{
                    //相等时有两种情况
                    if(j-i<=2){//如果其中元素小于等于三个,不用再判断一定是回文子串
                        arr[i][j]=true;
                    }else{
                        arr[i][j]=arr[i+1][j-1];
                    }

                    if(arr[i][j]){
                        if(j-i+1>maxLen){
                            //更新长度和其实下标
                            maxLen=j-i+1;
                            begin=i;
                        }
                    }
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
}
